

import java.util.*;
/**
 * 
 * 最长公共前缀
 * 
 * 描述

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： 
0
≤
n
≤
5000
0≤n≤5000， 
0
≤
l
e
n
(
s
t
r
s
i
)
≤
5000
0≤len(strs 
i
​	
 )≤5000
进阶：空间复杂度 
O
(
1
)
O(1)，时间复杂度 
O
(
n
∗
l
e
n
)
O(n∗len)

 */
public class 最长公共前缀 {
    
    public static void main(String[] args) {
        
        System.out.println(longestCommonPrefix(new String[]{"abca","abc","abca","abc","abcc"}));

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public static String longestCommonPrefix (String[] strs) {
        // write code here

        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }
}
